package cn.edu.jxau.test;

import java.awt.Cursor;
import java.util.NoSuchElementException;

/**
 * 基于有序链表的优先队列(priority queue)
 * insert:O(n)
 * delMax:O(n)
 * delMin:O(1)
 * 
 * @author 付大石
 */
public class SortedLinkedPQ {
    
    public static void main(String[] args) {

        SortedLinkedPQ pq = new SortedLinkedPQ();
        pq.insert(6);
        pq.insert(5);
        pq.insert(2);
        pq.insert(3);
        pq.insert(4);
        pq.insert(2);
        System.out.println(pq.delMax());
        System.out.println(pq.delMax());
        System.out.println(pq.delMin());
    }

    /**
     * 头结点
     */
    private Node head;

    /**
     * 优先队列元素个数
     */
    private int size;

    public SortedLinkedPQ() {
        head = new Node();
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    public void insert(int element) {

        Node node = new Node(element);
        Node current = head;
        while (current.next != null) {
            if (current.next.data >= element) {
                break;
            }
            current = current.next;
        }
        if (current.next == null) { // 最末端，element是当前pq中的最大值
            current.next = node;
        } else {
            node.next = current.next;
            current.next = node;
        }
        size++;
    }

    public int delMax() {

        if (isEmpty()) {
            throw new NoSuchElementException("优先队列为空");
        }
        Node pre = head;
        Node current = head.next;
        while (current.next != null) {
            pre = current;
            current = current.next;
        }
        int max = current.data;
        pre.next = null; // 删除最大的节点
        size--;
        return max;

    }

    public int delMin() {

        if (isEmpty()) {
            throw new NoSuchElementException("优先队列为空");
        }
        int min = head.next.data;
        head.next = head.next.next;
        return min;
    }

    private class Node {
        private int data;
        private Node next;

        public Node() {

        }

        public Node(int data) {
            this.data = data;
        }
    }
}
